package com.xzz.finger;

import java.util.List;

/**
 * @author: hhz
 * @create: 2022-02-16 13:55
 * 剑指 Offer 12. 矩阵中的路径
 **/
public class Exist {
    public static void main(String[] args) {
        System.out.println(exist(new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}},"ABCCED"));
    }

    public static boolean exist(char[][] board, String word) {
        char[] words  = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(dfs(i,j,0,board,words)){
                    return true;
                }
            }
        }
        return false;
    }
    public static boolean dfs(int i, int j, int k,char[][] board, char[] words) {
        if(i<0 || i>=board.length || j<0 ||j>=board[0].length){
            return false;
        }
        if(board[i][j] != words[k]){
            return false;
        }
        if(k == words.length - 1) {
            return true;
        }
        board[i][j] = ' ';
        boolean res = dfs(i+1,j,k+1,board,words)||dfs(i-1,j,k+1,board,words)||dfs(i,j+1,k+1,board,words)||dfs(i,j-1,k+1,board,words);
        board[i][j] = words[k];
        return res;

    }
}
